package cn.dlc.com.graph;

import cn.dlc.com.queue.Queue;
import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/31 7:10
 * @desc 加权无向图
 */
@Data
public class EdgeWeightedGraph {
    // 记录顶点数量
    private final int V;
    // 记录边数量
    private int E;
    // 邻接表
    private Queue<Edge>[] adj;

    public EdgeWeightedGraph(int V){
        this.V = V;
        this.E = 0;
        // 初始化邻接表
        this.adj = new Queue[V];
        // 初始化每一个邻接表
        for (int w = 0; w < V; w++) {
            adj[w] = new Queue<Edge>();
        }
    }

    // 获取图中顶点的数量
    public int V(){
        return this.V;
    }
    // 获取图中边的数量
    public int E(){
        return this.E;
    }
    // 向加权无向图中添加—条边
    public void addEdge(Edge e){
        // 获取两个顶点
        int v = e.getV();
        int w = e.other(v);

        // 添加边
        adj[v].enQueue(e);
        adj[w].enQueue(e);

        // 数量+1
        this.E++;
    }

    // 获取和顶点v关联的所有边
    public Queue<Edge> adj(int v){
        return this.adj[v];
    }
    // 获取加权无向图的所有边
    public Queue<Edge> edges(){
        // 创建一个队列，存放所有的边
        Queue<Edge> edges = new Queue<>();

        for (int i = 0; i < this.V; i++) {
            // 遍历所有的顶点
            for (Edge edge : this.adj[i]) {
                //因为这是无向图﹐所以同一条边同时出现在了它关联的两个顶点的邻接表中﹐
                // 需要让一条边只记录一次;
                if(edge.getV() < i) {
                    edges.enQueue(edge);
                }
            }
        }

        return edges;
    }
}
